package offer.offer01;

import java.util.Arrays;

/**
 *
 */
public class S07重建二叉树 {
    /**
     * 33, 递归改进版, 时间提升很多了, 内存也正常了。(虽然排名一般, 但是比复制快了五倍, 其实大家时间差不多。)
     * 使用四个标志位来标记子树的位置区间, 而不是复制。
     */
    public TreeNode buildTree2(int[] preorder, int[] inorder) {
        if(preorder.length == 0 | inorder.length == 0 | preorder.length != inorder.length) return null;
        return buildTree2(preorder, 0, preorder.length, inorder, 0, inorder.length);

    }
    // 可以用重载, 就不用想怎么命名了。这个好诶。
    public TreeNode buildTree2(int[] preorder, int start1, int end1, int[] inorder, int start2, int end2) {
        if(start1 == end1) return null;
        TreeNode root = new TreeNode(preorder[start1]);
        int rootPosi = start2; // 中序遍历的root位置, 即左右分界线
        for(int i = start2; i < end2; i++){
            if(inorder[i] == root.val){
                rootPosi = i;
                break;
            }
        }
        root.left = buildTree2(preorder, start1 + 1, start1 + (rootPosi - start2) + 1,
                inorder, start2, rootPosi);
        root.right = buildTree2(preorder, start1 + (rootPosi - start2) + 1, end1,
                inorder, rootPosi + 1, end2);
        return root;
    }
    /**
     * 18, 递归, Arrays.copyOfRange()消耗了大量时间, 同时空间复杂度也非常大(java居然能比标志位方式大一倍的使用空间)。
     * 应该使用位置标记来处理。注意这个方法取不到后面那个位置的值。
     * 因为没有相同的数, 所以可以通过找相同的数来做分割。然后根据长度来找子串。
     */
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if(preorder.length == 0 | inorder.length == 0 | preorder.length != inorder.length) return null;
        TreeNode root = new TreeNode(preorder[0]);
        int rootPosi = 0; // 中序遍历的root位置, 即左右分界线
        for(int i: inorder){
            if(i == root.val) break;
            rootPosi++;
        }
        if(rootPosi > 0)
            root.left = buildTree(Arrays.copyOfRange(preorder, 1, rootPosi + 1), Arrays.copyOfRange(inorder, 0, rootPosi));
        if(rootPosi < inorder.length - 1)
            root.right = buildTree(Arrays.copyOfRange(preorder, rootPosi + 1, preorder.length),
                    Arrays.copyOfRange(inorder, rootPosi + 1, inorder.length));
        return root;
    }

    /**
     * todo: 别人的方法。看官方题解迭代法。
     */
    private int in = 0;
    private int pre = 0;

    public TreeNode buildTree3(int[] preorder, int[] inorder) {
        return build(preorder, inorder, Integer.MIN_VALUE);
    }

    private TreeNode build(int[] preorder, int[] inorder, int stop) {
        if (pre >= preorder.length)
            return null;
        if (inorder[in] == stop) {
            in++;
            return null;
        }
        TreeNode node = new TreeNode(preorder[pre++]);
        node.left = build(preorder, inorder, node.val);
        node.right = build(preorder, inorder, stop);
        return node;
    }
}
